A portion of the disclosure of this patent document is submitted on one compact disc and is hereby incorporated herein by reference. The compact disc contains exactly one file, created on Jul. 2, 2002, which is named xe2x80x9csource-txtxe2x80x9d and is 75,040 bytes in size. An additional, identical compact disc is also included, for a total of two compact discs.
The invention relates to providing synchronization services for maintaining integrity of data accessed concurrently by both readers and writers.
In many information processing applications, multiple executing entities attempt to access data concurrently. For example, in a database program, multiple users may attempt to access the same database tables, records, and fields at the same time. Common examples of such database programs include software for processing class registrations at a university, travel reservations, money transfers at a bank, and sales at a retail business. In these examples, the programs may update databases of class schedules, hotel reservations, account balances, product shipments, payments, or inventory for actions initiated by the individual users. Sometimes a single program executes multiple threads accessing the same data concurrently. For example, one thread may watch for changes in data made by another thread.
However, data corruption may result when concurrent data access is uncontrolled. For example, consider the following scenario in which two computers, A and B, both attempt to remove one item from inventory by subtracting one from an inventory field in a database:
1. The inventory field value is xe2x80x9c2xe2x80x9d
2. Computer A reads the inventory field (xe2x80x9c2xe2x80x9d) to its local storage
3. Computer B reads the inventory field (xe2x80x9c2xe2x80x9d) to its local storage
4. Computer A subtracts xe2x80x9c1xe2x80x9d from its local storage, yielding xe2x80x9c1xe2x80x9d
5. Computer B subtracts xe2x80x9c1xe2x80x9d from its local storage, yielding xe2x80x9c1xe2x80x9d
6. Computer A writes its local storage (xe2x80x9c1xe2x80x9d) to the inventory field
7. Computer B writes its local storage (xe2x80x9c1xe2x80x9d) to the inventory field
8. The inventory field value is xe2x80x9c1xe2x80x9d
One would expect the value xe2x80x9c2xe2x80x9d to become xe2x80x9c0xe2x80x9d after two computers attempt to subtract xe2x80x9c1xe2x80x9d from it, but in the illustrated scenario, the result is instead xe2x80x9c1.xe2x80x9d Since the algorithm failed to take concurrency into account, the database has been corrupted. Such concurrency problems can arise whenever multiple executing entities (e.g., processes, tasks, threads, processors, or programming objects) access the same data.
Programmers have advanced a variety of approaches to address problems arising from concurrent processing. On a general level, many programming systems provide synchronization services to provide certain guarantees even in the face of concurrency. For example, some programming environments support simple synchronization mechanisms such as semaphores, locks, critical sections, and mutual exclusion objects (mutexes); each of these mechanisms controls concurrent access to a resource.
One particular concurrency scenario poses a special set of problems: sharing a resource between readers and writers. Since the readers do not modify the resource, it is commonly acceptable (and generally more efficient) to allow more than one of the readers to access the resource concurrently because there is no chance of data corruption. However, a writer is not permitted to write to (i.e., modify) the resource concurrently while another reader or writer is accessing the resource. Otherwise, the data may become corrupted as shown in the above example.
One approach to solving the reader/writer problem is to employ a synchronization mechanism called a semaphore. A semaphore is a value that multiple processes can check and change simultaneously, and logic associated with the semaphore guarantees the semaphore will not be corrupted. So, for example, the semaphore can be set to on (i.e., 1) or off (i.e., 0) to indicate whether or not a process is accessing the protected resource. Logic associated with the semaphore protects the semaphore from corruption by guaranteeing that two processes cannot simultaneously set the semaphore to on. Thus, a software developer can include logic referencing the semaphore in programming code. For example, a programmer could include logic that waits until a semaphore is off (i.e., 0) before writing to a resource. Thus, a later-in-time process must wait until a first-in-time process is finished with the resource; the later-in-time process then updates the semaphore accordingly to prevent others from writing to the resource.
Specifically, in the reader/writer context, a pair of semaphores can be used for each protected resource to track how many readers access the resource and whether there is a writer accessing the resource. Readers check the xe2x80x9cwhether there is a writerxe2x80x9d semaphore before proceeding, and writers check both the xe2x80x9cwhether there is a writerxe2x80x9d and xe2x80x9chow many readersxe2x80x9d semaphores before proceeding. However, the semaphore approach has several drawbacks.
First, in a system with many resources to protect, maintaining a pair of semaphores for each of the protected resources may consume excessive system resources. For example, in large database systems, it may require considerable computing power to administer the semaphores for the large number of database fields and tables in the system.
Second, the semaphore approach can lead to a problem called deadlock. Deadlock occurs when two or more processes (or threads) vie for two or more protected resources. For example, consider process A and process B, both of which require writing to fields Y and Z to update a database. Deadlock occurs under the following scenario:
1. Process A updates a semaphore protecting field Y to indicate Y is unavailable to other processes
2. Process B updates a semaphore protecting field Z to indicate Z is unavailable to other processes
3. Process A examines the semaphore protecting field Z and determines Z is unavailable (as noted by B), so process A waits for process B to release field Z
4. Process B examines the semaphore protecting field Y and determines Y is unavailable (as noted by A), so process B waits for process A to release field Y
5. Both processes wait forever
Although there are ways of dealing with the deadlock problem, such as conventional deadlock detection and conventional deadlock avoidance, again, considerable computing power is typically required to implement such solutions. Also, none of the solutions completely solves the problem. In light of the difficulty of solving the deadlock problem and the relative rarity of deadlock conditions, some systems ignore the deadlock problem altogether. However, such an approach can lead to a subtle software defect that is difficult to detect and debug.
Thus, an efficient synchronization mechanism for addressing the reader/writer scenario is needed, and a mechanism for avoiding the deadlock problem is needed.
The invention includes a method and system for providing reader/writer synchronization services using interlocked operations. Various features provided by the synchronization services lead to better use of resources and improved performance. The synchronization services manage the details of lock operation, freeing programmers from devoting time and resources to develop their own synchronization logic.
Data structures for implementing the reader/writer services can be maintained using an interlocked operation (e.g., an interlocked compare and exchange operation). Such an implementation is sometimes called xe2x80x9clocklessxe2x80x9d since logic to lock the data structures is not necessary. In addition, by maintaining some data structure elements in storage local to a thread, the lock services can more efficiently access lock state information.
In one arrangement, the system uses an execution suspension mechanism known as an event. The arrangement can thus be implemented on a variety of execution environments that support events.
In a just-in-time event creation feature, the system avoids excessive resource consumption by waiting until there is contention for a lock before creating an event. The event is then released when contention subsides. The system thus reduces the number of simultaneously-active events and reduces the total resources required in an implementation having multiple locks. Additionally, the events can be recycled (i.e., cached) by placing them into an event pool. In this way, the overhead for creating and destroying events is avoided.
A time out feature facilitates an optimistic deadlock avoidance scheme, providing programmers with a feature to address the deadlock problem. Various challenging programming pitfalls relating to implementing time outs are avoided.
For example, races particular to the time out arrangement are addressed to avoid lock corruption or inconsistency. Also, an event creation failure detection feature maintains stability and consistency of lock data structures in the face of insufficient available resources. The synchronization services are thus sufficiently robust for use in the kernel of an operating system or an execution engine.
In addition, the lock services support a set of features for componentized applications. For example, the services support upgrading a lock from reader status to writer status and downgrading a lock from writer status to reader status. Also, the lock can be suspended and restored. In these scenarios, information about intermediate writers (writers accessing the protected resource before the operation is complete) is provided. In addition, lock nesting can be tracked using thread-local storage, and certain nested requests can be monitored and automatically transformed to avoid deadlock.
Finally, a feature to improve efficiency on multiprocessor machines spins a lock request a small number of times before invoking an execution suspension mechanism. Thus, a context switch can be avoided.
Additional features and advantages of the invention will be made apparent from the following detailed description of illustrated embodiments, which proceeds with reference to the accompanying drawings.